package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
/**
 * @author: shm
 * @dateTime: 2020/11/2 8:51
 * @description: 349. 两个数组的交集
 * 给定两个数组，编写一个函数来计算它们的交集。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 * 示例 2：
 *
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 *
 *
 * 说明：
 *
 * 输出结果中的每个元素一定是唯一的。
 * 我们可以不考虑输出结果的顺序。
 */
public class Intersection {
    public int[] intersection(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        List<Integer> list = new ArrayList<>();
        if(n<=m){
            Arrays.sort(nums1);
            for(int i=0;i<n;i++){
                if(i>0&&nums1[i]==nums1[i-1]){
                    continue;
                }
                for(int j=0;j<m;j++){
                    if(nums1[i]==nums2[j]){
                        list.add(nums1[i]);
                        break;
                    }
                }
            }
        }else{
            return intersection(nums2,nums1);
        }
        int len = list.size();
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = list.get(i);
        }
        return arr;
    }

    /**
     * @author: shm
     * @dateTime: 2020/11/2 9:16
     * @description: 方法一：哈希表
     */
    public int[] intersection_2(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int i : nums1) {
            map.put(i,1);
        }
        for (int i : nums2) {
            if (map.containsKey(i)&&map.get(i)!=0){
                list.add(i);
                map.put(i,0);
            }
        }
        int len = list.size();
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = list.get(i);
        }
        return arr;
    }

    /**
     * @author: shm
     * @dateTime: 2020/11/2 9:15
     * @description: 方法二：排序 + 双指针
     */
    public int[] intersection_3(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i=0,j=0;
        int n = nums1.length;
        int m = nums2.length;
        List<Integer> list = new ArrayList<>();
        while (i<n&&j<m){
            if (nums1[i]==nums2[j]){
                list.add(nums1[i]);
                i++;
                while (i<n&&i>0&&nums1[i]==nums1[i-1]){
                    i++;
                }
                j++;
                while (j<m&&j>0&&nums2[j]==nums2[j-1]){
                    j++;
                }
            }else if (nums1[i]<nums2[j]){
                i++;
                while (i<n&&i>0&&nums1[i]==nums1[i-1]){
                    i++;
                }
            }else if (nums1[i]>nums2[j]){
                j++;
                while (j<m&&j>0&&nums2[j]==nums2[j-1]){
                    j++;
                }
            }
        }
        int len = list.size();
        int[] arr = new int[len];
        for(int k=0;k<len;k++){
            arr[k] = list.get(k);
        }
        return arr;
    }
}
